package BackTrack.Medium;

import java.util.LinkedList;
import java.util.List;

public class LC0022 {
    private class Path {
        int leftBracketCount = 0, rightBracketCount = 0;
        StringBuilder innerSb = new StringBuilder();
        LinkedList<String> innerList = new LinkedList<>();

        void appendToken(String token) {
            if (token.equals("(")) {
                innerList.add(token);
                leftBracketCount++;
            } else if (token.equals(")")) {
                innerList.add(token);
                rightBracketCount++;
            }
        }

        void removeLast() {
            String token = innerList.removeLast();
            if (token.equals("(")) leftBracketCount--;
            else rightBracketCount--;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            for (String str : innerList) sb.append(str);
            return sb.toString();
        }
    }

    LinkedList<String> results = new LinkedList<>();
    int N;

    public List<String> generateParenthesis(int n) {
        N = n;
        innerRecursive(new Path());
        return results;
    }

    private void innerRecursive(Path path) {
        if (path.innerList.size() == 2 * N) {
            results.add(path.toString());
            return;
        }

        if (path.leftBracketCount < N) {
            path.appendToken("(");
            innerRecursive(path);
            path.removeLast();
        }

        if (path.rightBracketCount < path.leftBracketCount) {
            path.appendToken(")");
            innerRecursive(path);
            path.removeLast();
        }
    }
}
